<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>二维数组查找</title>
</head>
<body>
    
</body>
</html>

<script>
    /**
     * 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
     * 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
     *   1 2 3
     *   4 5 6
     *   7 8 9
     * **/

    // 1. 第一种，利用x y 坐标去找
    function finNum(target, arr) {
        let x = 0;
        let y = arr.length -1;
        return compare(target, arr , x, y)
    }

    function compare(target, arr, x, y) {
        if(arr[x] === undefined || arr[y] === undefined) {
            return false
        }

        let tempNum = arr[y][x];

        if(tempNum === target) {
            return true;
        }

        if(tempNum< target) {
            return compare(target, arr, x+1, y)
        }

        if(tempNum > target) {
            return compare(target, arr, x, y-1);
        }
    }

    let temparray = [
        [1,2,3],
        [4,5,6],
        [7,8,9]
    ]

    console.log(finNum(9,temparray))

    //2. 第二种，利用二分法去查找

/*
    二分法查找的必要条件： 必须有序， 然后跟线性表中的中点值进行比较
*/
function binarySearch(data, arr, start, end) {
    if(arr[start] === undefined || arr[end] === undefined) return false;
    if(start > end) {
        return -1;
    }

    let mid = Math.floor((start + end)/2);
    if(data === arr[mid]) return true;

    if(data < arr[mid]) {
        return binarySearch(data, arr, start, mid -1);
    }

    if(data > arr[mid]) return binarySearch(data, arr, mid+1, end)
}

let newTempArr = [...temparray[0],...temparray[1],...temparray[2]];
console.log(newTempArr)

console.log(binarySearch(10, newTempArr, newTempArr[0], newTempArr[newTempArr.length-1]))
</script>